import java.util.HashMap;

// 判定是否互为字符重排
//https://leetcode.cn/problems/check-permutation-lcci/description/
public class Test {
    public static void main(String[] args) {
        //
    }
}


//方法1：数组模拟哈希表
class Solution1 {
    public boolean CheckPermutation(String s1, String s2) {
        //
        if (s1.length() != s2.length()) {
            return false;
        }
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            hash1[s1.charAt(i) - 'a']++;
        }
        for(int i = 0; i < s2.length(); i++){
            hash2[s2.charAt(i) - 'a']++;
        }
        for(int i = 0; i < 26; i++){
            if(hash1[i] != hash2[i]){
                return false;
            }
        }
        return true;
    }
}


//方法2：哈希表
class Solution2 {
    public boolean CheckPermutation(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 != len2) {
            return false;
        }

        HashMap<Character, Integer> map1 = new HashMap<>();//<字符，个数>
        HashMap<Character, Integer> map2 = new HashMap<>();
        for(int i = 0; i < s1.length(); i++){
            map1.put(s1.charAt(i), map1.getOrDefault(s1.charAt(i), 0) + 1);
        }
        for(int i = 0; i < s2.length(); i++){
            map2.put(s2.charAt(i), map2.getOrDefault(s2.charAt(i), 0) + 1);
        }
        for(int i = 0; i < s1.length(); i++){
            if(map1.containsKey(s1.charAt(i))&&map2.containsKey(s1.charAt(i))){
                if(map1.get(s1.charAt(i))!=map2.get(s1.charAt(i))){
                    return false;
                }
            }else{
                return false;
            }
        }
        return true;

    }
}

//方法3：哈希表的优化（只用一个哈希表就完成）
class Solution3cunzaichogfuuansuiiyiyangdehaxvyaoduotogjiyigexixihanu ms[k] {
    public boolean CheckPermutation(String s1, String s2) {
        //
        int len1 = s1.length();
        int len2 = s2.length();
        if (len1 != len2) {
            return false;
        }

        HashMap<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < s1.length(); i++){
            map.put(s1.charAt(i), map.getOrDefault(s1.charAt(i), 0) + 1);
        }
        for(int i = 0; i < s2.length(); i++){
            map.put(s2.charAt(i), map.getOrDefault(s2.charAt(i), 0) - 1);
        }
        for(int i = 0; i < s1.length(); i++){
            if(map.get(s1.charAt(i))!=0){
                return false;
            }
        }
        return true;
    }
}
//方法4：看完老师的代码，进一步优化
class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if(s1.length() != s2.length()) return false;
        int[] hash = new int[26];
        for(int i = 0; i<s1.length();i++){
            hash[s1.charAt(i)-'a']++;
        }

        for(int i = 0;i<s2.length();i++){
            int tmp = --hash[s2.charAt(i)-'a'];//注意：这里的--，要放在前边！！！
            if(tmp<0) return false;
        }
        return true;
    }
}
